Prim's অ্যালগরিদম
Prim's অ্যালগরিদম হলো একটি গ্রাফ তত্ত্বের অ্যালগরিদম, যা একটি কানেক্টেড গ্রাফের মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree বা MST) বের করতে ব্যবহৃত হয়। MST হলো একটি উপগ্রাফ, যেখানে সমস্ত নোড কানেক্ট থাকে এবং এটির মোট প্রান্তের ওজন সবচেয়ে কম হয়।
Prim's অ্যালগরিদমটি ধীরে ধীরে নোড যোগ করে MST গঠন করে। এটি সাধারণত গ্রাফের একটি নির্দিষ্ট নোড থেকে শুরু করে এবং তার আশেপাশের প্রান্তের মধ্যে সর্বনিম্ন ওজনের প্রান্তটি নির্বাচন করে চলতে থাকে, যতক্ষণ না সমস্ত নোড কাভার হয়।
Prim's অ্যালগরিদমের ধাপসমূহ:
- প্রথমে একটি আর্বিট্রারি নোড নির্বাচন করে সেটিকে MST-তে অন্তর্ভুক্ত করুন।
- MST-তে থাকা নোডগুলোর সাথে যেকোনো কানেক্টেড প্রান্তের মধ্যে সর্বনিম্ন ওজনের প্রান্ত নির্বাচন করুন এবং সংশ্লিষ্ট নোডটিকে MST-তে যোগ করুন।
- পুনরাবৃত্তি চালিয়ে যান যতক্ষণ না সমস্ত নোড MST-তে অন্তর্ভুক্ত হয়।
উদাহরণ:
ধরি, একটি গ্রাফ আছে, যেখানে নোড এবং তাদের মধ্যে প্রান্তগুলির ওজন রয়েছে। Prim's অ্যালগরিদমের সাহায্যে নিম্নতম ওজনের স্প্যানিং ট্রি তৈরি করতে গ্রাফের যেকোনো একটি নোড থেকে শুরু করে প্রক্রিয়াটি সম্পন্ন করা হয়।
Prim's অ্যালগরিদম সাধারণত O(V^2) জটিলতায় কাজ করে, যেখানে V হলো নোডের সংখ্যা।
Kruskal's অ্যালগরিদম
Kruskal's অ্যালগরিদম আরেকটি গ্রাফ তত্ত্বের অ্যালগরিদম, যা মিনিমাম স্প্যানিং ট্রি (MST) বের করতে ব্যবহৃত হয়। তবে Prim's এর থেকে এটি ভিন্ন, কারণ Kruskal's অ্যালগরিদম প্রতিটি নোড থেকে প্রান্ত যোগ না করে বরং প্রান্তগুলিকে ওজনের ক্রম অনুযায়ী সাজিয়ে সবচেয়ে কম ওজনের প্রান্ত থেকে MST গঠন শুরু করে।
Kruskal's অ্যালগরিদমের ধাপসমূহ:
- সমস্ত প্রান্ত ওজন অনুযায়ী সাজান।
- প্রান্তগুলো থেকে ক্রমানুসারে সর্বনিম্ন ওজনের প্রান্ত নির্বাচন করুন এবং এটি MST-তে যোগ করুন, যদি এটি কোনো সাইকেল তৈরি না করে।
- প্রক্রিয়াটি চালিয়ে যান যতক্ষণ না সমস্ত নোড সংযুক্ত হয় এবং MST গঠন সম্পন্ন হয়।
উদাহরণ:
ধরি, একটি গ্রাফ আছে, যেখানে বিভিন্ন প্রান্ত এবং তাদের ওজন নির্ধারিত। Kruskal's অ্যালগরিদমে প্রান্তগুলোকে ওজন অনুযায়ী সাজিয়ে সবচেয়ে কম ওজনের প্রান্ত থেকে শুরু করে কাজ করা হয়।
Kruskal's অ্যালগরিদম সাধারণত O(E log E) জটিলতায় কাজ করে, যেখানে \(E\) হলো প্রান্তের সংখ্যা।
Prim's বনাম Kruskal's অ্যালগরিদম
| বৈশিষ্ট্য | Prim's অ্যালগরিদম | Kruskal's অ্যালগরিদম |
|---|---|---|
| প্রান্ত নির্বাচন | নোডের আশেপাশের সর্বনিম্ন ওজনের প্রান্ত | সর্বনিম্ন ওজনের প্রান্ত নির্বাচন |
| ব্যবহৃত স্ট্রাকচার | মিন-হিপ বা প্রায়োরিটি কিউ | প্রান্তের লিস্ট |
| সাইকেল চেক | সরাসরি লাগে না | সাইকেল চেক প্রয়োজন |
| কার্যকারিতা | ঘন গ্রাফে বেশি কার্যকরী | বিচ্ছিন্ন গ্রাফে বেশি কার্যকরী |
Prim's এবং Kruskal's উভয় অ্যালগরিদমই MST বের করতে ব্যবহৃত হয়, তবে Prim's সাধারণত ঘন গ্রাফে বেশি কার্যকরী, এবং Kruskal's কম প্রান্তবিশিষ্ট গ্রাফে বেশি কার্যকরী।
Read more
